import java.util.List;

public class MySingleList implements IList{
    //定义节点类
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    //定义链表的头节点
    public ListNode head;//默认为null

    //创建一个链表
    public void createList() {
        //先创建4个节点
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(12);
        ListNode node3 = new ListNode(12);
        ListNode node4 = new ListNode(45);

        //再将4个节点进行连接
        this.head = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
    }
    //打印链表
    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //清空链表
    @Override
    public void clear() {
        head = null;
    }

    //链表的长度
    @Override
    public int size() {
        int num = 0;
        ListNode cur = head;
        while(cur != null) {
            num++;
            cur = cur.next;
        }
        return num;
    }

    //删除所有值为key的元素
    @Override
    public void removeAllKey(int key) {
        //空链表
        if(head == null) {
            return;
        }
        //头删
        if(key == head.val) {
            head = head.next;
        }
        //移除后面的元素
        ListNode cur = head;
        ListNode curPrev = head;
        while(cur != null) {
            if(cur.val == key) {
                curPrev.next = cur.next;
                cur = cur.next;
            } else {
                curPrev = cur;
                cur = cur.next;
            }

        }
    }

    //删除第一个值为key这个元素
    @Override
    public void remove(int key) {
        //空链表
        if(head == null) {
            return;
        }
        //头删
        if(key == head.val) {
            head = head.next;
            return;
        }
        //移除后面的元素
        ListNode cur = head;
        ListNode curPrev = head;
        while(cur != null) {
            if(cur.val == key) {
                curPrev.next = cur.next;
                return;
            }
            curPrev = cur;
            cur = cur.next;
        }
    }

    //链表中是否存在key这个元素
    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key)
                return true;
            cur = cur.next;
        }
        return false;
    }

    //index下标处插入元素data
    @Override
    public void addIndex(int index, int data) {
        ListNode node = new ListNode(data);
        if(index == 0|| index >size()-1) {
            throw new IndexException("index不合法："+ index);
        }
        //空链表头插
        if (head == null) {
            head = node;
            return;
        }
        //中间插入
        int count = 0;
        ListNode cur = head;
        while(cur.next != null) {
            count++;
            if(count == index) {
                node.next = cur.next;
                cur.next = node;
                return;
            }
            cur = cur.next;
        }
        //尾插
        if(index ==size()-1) {
            addLast(data);
            return;
        }
    }

    //尾插
    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        //考虑特殊情况：空链表
        if(head == null) {
            head = node;
        } else {
            //得到最后一个节点cur
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //头插
    @Override
    public void addFirst(int data) {
        //创建一个节点
        ListNode node = new ListNode(data);

        node.next = this.head;
        this.head = node;
    }

}
